// 你是一个专业的小偷，计划偷窃沿街的房屋。
// 每间房内都藏有一定的现金，
// 影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，
// 如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
// 给定一个代表每个房屋存放金额的非负整数数组，
// 计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/house-robber
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
/**
 * @param {number[]} nums
 * @return {number}
 */
var rob = function (nums) {
  const len = nums.length
  const dp = new Array(len - 1).fill(0)
  dp[0] = nums[0]
  dp[1] = Math.max(nums[0], nums[1])
  for (let i = 2; i < len; i++) {
    const p1 = dp[i - 2] + nums[i]
    const p2 = dp[i - 1]
    dp[i] = Math.max(p1, p2)
  }

  return dp[len - 1]

  // 1. 从 0 到 i 的房间，能偷到的最大值
  const helper = (i) => {
    // 4. base case 由题目分析，i === 0 只有一个房间可偷
    // i === 1 表示有两个房间，从最大值中偷
    if (i === 0) {
      return nums[0]
    }
    // 因为 helper 依赖 helper(i - 2) 所以 i >= 2，
    // base case 就包含了 i < 2 也就是 i = 0, i = 1 的情况
    if (i === 1) {
      return Math.max(nums[0], nums[1])
    }

    // 3. helper(i) 是同 helper(i - 1) 和 helper(i - 2) 推导出来的
    const p1 = helper(i - 2) + nums[i]
    const p2 = helper(i - 1)

    return Math.max(p1, p2)
  }
  // 2. i 的范围应该是从 0 到 nums.length - 1
  const res = helper(len - 1)

  return res
}

console.log(
  rob([1, 2, 3, 1])
)